Two sum IV [BST]

Time: O(N); Space: O(H); medium

Given a Binary Search Tree and a target number,

return True if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

    5
   / \
  3   6
 / \   \
2   4   7

Input: root = {TreeNode} [5,3,6,2,4,None,7], target = 9

Output: True

Example 2:

    5
   / \
  3   6
 / \   \
2   4   7

Input: root = {TreeNode} [5,3,6,2,4,None,7], target = 28

Output: False

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Using BST

Algorithm

In this approach, we make use of the fact that the given tree is a Binary Search Tree. Now, we know that the inorder traversal of a BST gives the nodes in ascending order. Thus, we do the inorder traversal of the given tree and put the results in a listlist which contains the nodes sorted in ascending order.

Once this is done, we make use of two pointers ll and rr pointing to the beginning and the end of the sorted listlist. Then, we do as follows:

Check if the sum of the elements pointed by ll and rr is equal to the required sum kk. If so, return a True immediately.

Otherwise, if the sum of the current two elements is lesser than the required sum kk, update ll to point to the next element. This is done, because, we need to increase the sum of the current elements, which can only be done by increasing the smaller number.

Otherwise, if the sum of the current two elements is larger than the required sum kk, update rr to point to the previous element. This is done, because, we need to decrease the sum of the current elements, which can only be done by reducing the larger number.

Continue steps 1. to 3. till the left pointer ll crosses the right pointer rr.

If the two pointers cross each other, return a False value.

Note that we need not increase the larger number or reduce the smaller number in any case. This happens because, in case, a number larger than the current list[r]list[r] is needed to form the required sum kk, the right pointer could not have been reduced in the first place. The similar argument holds true for not reducing the smaller number as well.

[5]:

class Solution1(object):
    def findTarget(self, root, k) -> bool:
        '''
        :type root: TreeNode
        :type k: int
        :rtype: bool
        '''
        class BSTIterator(object):
            def __init__(self, root, forward):
                self.__node = root
                self.__forward = forward
                self.__s = []
                self.__cur = None
                self.next()

            def val(self):
                return self.__cur

            def next(self):
                while self.__node or self.__s:
                    if self.__node:
                        self.__s.append(self.__node)
                        self.__node = self.__node.left if self.__forward else self.__node.right
                    else:
                        self.__node = self.__s.pop()
                        self.__cur = self.__node.val
                        self.__node = self.__node.right if self.__forward else self.__node.left
                        break


        if not root:
            return False

        left, right = BSTIterator(root, True), BSTIterator(root, False)

        while left.val() < right.val():
            if left.val() + right.val() == k:
                return True
            elif left.val() + right.val() < k:
                left.next()
            else:
                right.next()
        return False

[6]:

s = Solution1()

root = TreeNode(5)
root.left, root.right = TreeNode(3), TreeNode(6)
root.left.left, root.left.right = TreeNode(2), TreeNode(4)
root.right.rihght = TreeNode(7)

target = 9
assert s.findTarget(root, target) == True

target = 28
assert s.findTarget(root, target) == False